/*
const sum = (n) => {
    let s = 0
    for (let i = 0; i < n; i++) {
        s += i
    }
    return s
}
let start = Date.now()
console.log(sum(10))
console.log(sum(500))
let end = Date.now()
console.log(end - start, ': 毫秒')



const sum = (n) => {
    let s = 0
    for (let i = 0; i < n; i++) {
        s += f(n)
    }
}

const f = (n) => {
    let s = 0
    for (let i = 0; i < n; i++) {
        s ++
    }
    return s
}

*/
// O(logn)
// const sum = (n) => {
//     let s = 0
//     for (let i = 0; i < n; i++) {
//         if (i % 3 === 0) {
//             i += 10 //加速
//         }
//         s++
//     }
//     return s
// }

// console.log(
//     sum(100)
// )

// O(nlogn)
/*

const sum = (n) => {
    let s = 0
    for (let i = 0; i < n; i++) {
        for (let j = 0;j < n; j++) {
            j += 2 // 加速
            s++
        }
    }
    return s
}

console.log(
    sum(100)
)


const sum = (n, m) => {
    let s = 0
    let q = 0
    for (let i = 0; i < n;i++) {
        s ++
    }
    for (let i = 0; i < m;i++) {
        q ++
    }
    return {s, q}
}
*/
// O(m+n)

// 空间复杂度
// O(lgon)
/*
const sum = (n) => {
    let a = []
    for (let i = 0; i < n; i++) {
        if (i % 5 === 0) {
            a.push(i)
        }
    }
    return a
}
*/

// O(n)
/*
const sum = (n) => {
    let a = []
    for (let i = 0; i < n; i++) {
        a.push(i)
    }
    return a
}
*/

// O(nlogn)

/*
const sum = (n) => {
    let a = []
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (j % 5 === 0) {
                a.push(j)
            }
        }
    }
    return a
}
*/
// O(n2)
/*
const sum = (n) => {
    let a = []
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            a.push(j)
        }
    }
    return a
}


const find = (arr, n) => {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === n) {
            return i
        }
    }
    return -1
}

let arr = [1,2,3,4,5,6,7,8,9, ]

find(arr, 1) // O(1)  最好情况
find(arr, 9) // O(n)  
find(arr, 100) // O(n) 最坏情况
*/

// 平均情况时间复杂度
/*
    let arr = [1,2,3,4,5,6,7,8,9, // 10000]
    n 是随机数

    find(arr, 100): n * 0.1
    find(arr, 200): n * 0.2
    find(arr, 10): n * 0.01
    find(arr, 10000): n * 1

    平均时间复杂度: 速度的综合 / 执行的次数 ≈ 1 = O(n)
*/

// 0
// 1 1
// 1 1
// 1 1
// 1 1
// 1 1

// 均摊时间复杂度
const add = (arr, a, n) => { // O(1)
    arr.push(a)
    // 删除 arr 元素
    if (arr.length > n) {
        for (let i = 0; i < n; i++) {
            arr.splice(1, 1)
        }
    }
    return arr
}
let arr = []
for (let i = 0; i < 210; i++) {
    arr = add(arr, 1, 100)
}

console.log(
    arr,
    arr.length
)
